#include "stack_queue.h"
#include <iostream>
#include <string>

listNode::listNode(){
    data = 0;
    next = NULL;
};
listNode::~listNode() = default;
listNode::listNode(int nodeData, listNode* succ){
    data = nodeData;
    next = succ;
}

chNode::chNode(){
    data = ' ';
    next = NULL;
};
chNode::~chNode() = default;
chNode::chNode(char nodeData, chNode* succ){
    data = nodeData;
    next = succ;
}



MyStack::MyStack()
{
    stackSize = 0;
    topNode = NULL;
}

MyStack::~MyStack(){
    while(topNode != NULL){
        auto node = topNode;
        topNode = topNode -> next;
        delete node;
        node = NULL;
    }
    stackSize = 0;
    topNode = NULL;
}

bool MyStack::push(const int& item){
    listNode* p = new listNode(item, NULL);
    p -> next = topNode;
    topNode = p;
    stackSize ++;
    return true; 
}

bool MyStack::pop(int& output){
    if(stackSize == 0)
        return false;
    output = topNode -> data;
    auto p = topNode;
    topNode = topNode -> next;
    delete p;
    stackSize --;
    return true;
}

bool MyStack::getTop(int& a){
    if(stackSize == 0)
        return false;
    a = topNode -> data;
    return true;
}

void MyStack::printStack(){
    listNode* p = topNode;
    while(p != NULL){
        if(p -> next == NULL)
            std::cout << p->data << std::endl;
        else
            std::cout << p->data << ",";
        p = p->next;
    }
}

MyQueue::MyQueue() = default;
MyQueue::MyQueue(const int& a){
    capacity = a;
    front = 0;
    rear = 0;
    queue = new int[capacity];
}

MyQueue::~MyQueue(){
    delete [] queue;
    front = 0, rear = 0;
    capacity = 0;
}

bool MyQueue::enQueue(const int& a){
    if((rear + 1) % capacity == front)
        return false;
    queue[rear] = a;
    rear = (rear + 1) % capacity;
    return true; 
}

bool MyQueue::deQueue(int& a){
    if(front == rear)
        return false;
    a = queue[front];
    queue[front] = 0;
    front = (front + 1) % capacity;
    return true;
}

bool MyQueue::getFront(int& a){
    if(front == rear)
        return false;
    a = queue[front];
    return true;
}

bool MyQueue::isFull(){
    if((rear + 1) % capacity == front)
        return true;
    return false;
};

void MyQueue::printQueue(){
    int cursor = front;

    while(cursor != rear)
    {
        if((cursor + 1) % capacity == rear)
            std::cout << queue[cursor] << std::endl;
        else
            std::cout << queue[cursor] << ",";

        cursor = (cursor + 1) % capacity;
    }
}

int inoppower(char ch){
    switch(ch){
        case '+':
        case '-':
            return 3;
        case '*':
        case '/':
            return 5;
        case '(':
            return 1;
        case ')':
            return 6;
        case '#':
            return 0;
        default:
            return false;
        }
}

int outoppower(char ch){
    switch(ch){
        case '+':
        case '-':
            return 2;
        case '*':
        case '/':
            return 4;
        case '(':
            return 6;
        case ')':
            return 1;
        default:
            return false;
        }
}

OPStack::OPStack()
{
    stackSize = 0;
    topNode = NULL;
}

OPStack::~OPStack(){
    while(topNode != NULL){
        auto node = topNode;
        topNode = topNode -> next;
        delete node;
        node = NULL;
    }
    stackSize = 0;
    topNode = NULL;
}

bool OPStack::push(const char& item){
    chNode* p = new chNode(item, NULL);
    p -> next = topNode;
    topNode = p;
    stackSize ++;
    return true; 
}

bool OPStack::pop(char& output){
    if(stackSize == 0)
        return false;
    output = topNode -> data;
    auto p = topNode;
    topNode = topNode -> next;
    delete p;
    stackSize --;
    return true;
}

char OPStack::getTop( ){
    if(stackSize == 0)
        return false;
    char a = ' ';
    a = topNode -> data;
    return a;
}

bool postfixExpression(const std::string& s1, std::string& s2){
    s2 = "";
    OPStack Opera;
    Opera.push('#');
    int s2i = 0;
    for(int i = 0; i < s1.length(); i ++){
        if(isdigit(s1[i])){
            s2.append(1, s1[i]);
            s2i ++;
            continue;
            }
        char item = ' ';
        int out = 0;
        int in = 0;
        if(outoppower(s1[i])){
            out = outoppower(s1[i]);
            in = inoppower(Opera.getTop());
        }
        else{
            s2 = "Expression is wrong!";
            return false;
        }
        if(out == in){
            Opera.pop(item);
            continue;
        }
        else if(out > in){
            Opera.push(s1[i]);
        }
        else if(in > out){
            Opera.pop(item);
            if(item == ')' || item == '('){
                s2 = "Expression is wrong!";
                return false;
            }
            s2.append(1, item);
            i --;
        }
        }
    while(Opera.getTop() != '#'){
        char last;
        Opera.pop(last);
        if(last == '('){
            s2 = "Expression is wrong!";
            return false; 
        }
        if(last == ')'){
            if(Opera.getTop() == '(')
            Opera.pop(last);
            else{
            s2 = "Expression is wrong!";
            return false;
            }
            continue;
        }
        s2.append(1, last);  
    }
    return true;
};

float compute(int a, int b, char c){
    switch (c)
    {
    case '+':
        return a + b;
        break;
    case '-':
        return a - b;
    case '*':
        return a * b;
    case '/':
        return a / b;
    default:
        break;
    }
}

bool expressionVal(const std::string& s1, int& output){
    std::string s2 = "";
    MyStack ms;
    if(postfixExpression(s1, s2)){
        for(int i = 0; i < s2.length(); i ++){
            if(isdigit(s2[i])){
            ms.push(s2[i] - 48);
            int a = 0;
            ms.getTop(a);
            continue;
            }
            else{
                int a = 0, b = 0, c = 0;
                ms.pop(b);
                ms.pop(a);
                c = compute(a, b, s2[i]);
                ms.push(c);
            }
        }
        ms.getTop(output);
        return true;
    }
    output = 0;
    return false;
};

void yanghui(const int& yang){
    MyQueue mq(yang + 2);
    mq.enQueue(1);
    mq.enQueue(1);
    mq.printQueue();
    for(int i = 0; i < yang - 1; i ++){
        for(int j = 0; j < i + 1; j ++){
        int a = 0, b = 0, c = 0;
        mq.deQueue(a);
        mq.getFront(b);
        c = a + b;
        mq.enQueue(c);
        }
        mq.enQueue(1); 
        mq.printQueue();
    }
};    

